﻿// 0810train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <limits>

using namespace std;


/*
 有 number 种商品，由于仓库限制每件商品的最大持有数量是 item[index]，
 每种商品的价格在每天是 item_price[item_index][day]，
 通过对商品的买进和卖出获取利润，请给出商人在 days 天内能获取到的最大的利润

number = 3，days = 3，item = [4，5，6]，item_price = [[1，2，3]，[4，3，2]，[1，5，3]]

- 针对第一件商品，商人在第一天的价格是 item_price[0][0] = 1 时买入 item[0]件，在第三天 item_price[0][2] = 3 的时候卖出，获利最大是 8；
- 针对第二件商品，不进行交易，获利最大是 0；
- 针对第三件商品，商人在第一天的价格是 item_price[2][0] = 1 时买入 item[2]件，在第二天 item_price[2][0] == 5 的时候卖出，获利最大是 24；
因此这段时间商人能获取的最大利润是 8 + 24 = 32；

[
[1，2，3]，
[4，3，2]，
[1，5，3]
]
d==0
dynamic[i][0][0]=0
dynamic[i][0][1]=-item_price[i][0]


第d天无 d-1天无/d-1天有，d天卖
dynamic[i][d][0]=max(dynamic[i][d-1][0],dynamic[i][d-1][1]+item_price[i][d]

第d天有 d-1天有/d-1天无，d天买
dynamic[i][d][1]=max(dynamic[i][d-1][1]，dynamic[i][d-1][0]-item_price[i][d]
 */

void solve01(vector<int>&item_limit_vec, vector<vector<int>>&item_prices)
{
    int item_size = item_prices.size();
    int day_size = item_prices[0].size();

    vector<int>status_vec = { 0,0 };
    vector<vector<int>>day_vec(day_size, status_vec);
    vector<vector<vector<int>>>dynamic_grid(item_size, day_vec);

    for (int i=0; i<item_size; i++)
    {
        //0天无，利润为0
        dynamic_grid[i][0][0] = 0;
        //0天有，买入item
        dynamic_grid[i][0][1] = -item_prices[i][0];
        //for---
    }

    for (int i=0; i<item_size; i++)
    {
        for (int d=1; d<day_size; d++)
        {
            //第d天无 d - 1天无 / d - 1天有，d天卖
        	//dynamic[i][d][0] = max(dynamic[i][d - 1][0], dynamic[i][d - 1][1] + item_prices[i][d]

            int max_prev_0 = max(dynamic_grid[i][d - 1][0], dynamic_grid[i][d - 1][1] + item_prices[i][d]);
            dynamic_grid[i][d][0] = max_prev_0;

            //第d天有 d - 1天有 / d - 1天无，d天买
        	//dynamic[i][d][1] = max(dynamic[i][d - 1][1]，dynamic[i][d - 1][0] - item_prices[i][d]
            int max_prev_1 = max(dynamic_grid[i][d - 1][1], dynamic_grid[i][d - 1][0] - item_prices[i][d]);
            dynamic_grid[i][d][1] = max_prev_1;

        }
    }
    //最大利润
    int result = 0;
    for (int i=0; i<item_size; i++)
    {
        int curr_num = dynamic_grid[i][day_size - 1][0];
        if (curr_num>0)
        {
            //货物数量
            int count = item_limit_vec[i];
            result += (curr_num * count);
        }
    }
    cout << result;
    //solve01
}


/*
给你一个只包含正整数的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2:
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。
 */

int solve02(vector<int>& nums)
{
    vector<int>oh_vec = nums;
    //目标sum/2
    int sum = 0;
    for (auto&num:oh_vec)
    {
        sum += num;
    }
    if (sum % 2 != 0) return false;

    sum = sum / 2;
    //边界情况
	//容量为0时，true成立
    //dp[i][0]=true 
    //可选择为0时，false不成立
    //dp[0][w]=true
    int vec_size = nums.size();
    int sum_size = sum + 1;
    vector<vector<int>>dynamic_grid(vec_size, vector<int>(sum_size,false));
    for (int i=0; i<vec_size; i++)
    {
        dynamic_grid[i][0] = true;
    }

    for (int i=1; i<vec_size; i++)
    {
	    for (int w=1; w<sum_size; w++)
	    {
            //转移方程
            //当前i容量超出
            if (w < nums[i])
            {
                dynamic_grid[i][w] = dynamic_grid[i - 1][w];
            }
            else
            {
                //1不装入nums[i] dp[i-1][w]
                //2装入nums[i] dp[i-1][w-nums[i-1]]
                dynamic_grid[i][w] = dynamic_grid[i - 1][w] || dynamic_grid[i - 1][w - nums[i]];
            }

	    }
    }

    return dynamic_grid[vec_size-1][sum];
    //solve02
}


/*
 给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
 */

int solve03(vector<int>& nums, int target) {
    //sum=positive+negative
    //target=positive-negative
    //positive=(sum+target)/2
    int sum = 0;
    for (int i=0; i<nums.size(); i++)
    {
        sum += i;
    }
    int pos_sum = (sum + target) / 2;
    //计算前i个数字中，能取到positive的个数有几种
    //注意这里+1，nums.size()要取到
    int dp_size = nums.size()+1;
    vector<vector<int>>dynamic_vec(dp_size, vector<int>(pos_sum));
    //边界情况，凑出0，一个positive都不能取
    for (int i=0; i<dp_size; i++)
    {
        dynamic_vec[i][0] = 0;
    }

    for (int i=0;i<dp_size; i++)
    {
	    
    }

    return 0;
    //solve03------
}


/*
 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。

示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
 */

int DpCoins(vector<int>& coins, int amount)
{
    //凑出0，需要0个
    if (amount == 0) return 0;
    if (amount < 0) return -1;


    int res = INT_MAX;
    for (auto&coin:coins)
    {
        int subProblem = DpCoins(coins, amount - coin);
        if (subProblem == -1) continue;
        res = min(res, subProblem + 1);
    }

    return res;
    //DpCoins
}

int solve04(vector<int>&coins, int amount)
{
    return DpCoins(coins, amount);
    //solve04
}


int solve05(vector<int>& coins, int amount)
{
    //转移方程
    //dp[i]=min(dp[i],dp[i-coin])
    //这里要取到amount，凑出amount所需的数量嘛
    //初值全部设为amount+1, 模拟INT_MAX的情况
    int dp_size = amount + 1;
    vector<int>dynamic_vec(dp_size, amount + 1);
	//凑出0 0个硬币
    dynamic_vec[0] = 0;

    for (int i=1; i<dp_size; i++)
    {
        for (auto&coin:coins)
        {
            if (i-coin < 0)
            {
                //子问题无解
                continue;
            }
            //子问题有解才赋值
            dynamic_vec[i] = min(dynamic_vec[i], 1 + dynamic_vec[i - coin]);
        }
    }

    if (dynamic_vec[amount]==amount+1)
    {
        return -1;
    }

    return dynamic_vec[amount];
    //solve05------
}


/*
 给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。 
题目数据保证结果符合 32 位带符号整数。

示例 1：
输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
 */

int solve06(int amount, vector<int>& coins)
{
    if (coins.size()==1)
    {
        if (amount % coins[0] == 0) return 1;
        return 0;
    }

    int dp_size = coins.size() + 1;
    int amount_size = amount + 1;
    vector<int>amount_vec(amount_size, 0);
    vector<vector<int>>dynamic_grid(dp_size, amount_vec);

    for (int i=0; i<dp_size; i++)
    {
	    //凑出金额0，无论如何有1种解法
        dynamic_grid[i][0] = 1;
    }

    //i==0, coins前0个数中, 0种解法
    for (int i=1; i<dp_size; i++)
    {
        for (int w=1; w<amount_size; w++)
        {
            if (w-coins[i-1]<0)
            {
                //<0，肯定不能选coins[i]
                dynamic_grid[i][w] = dynamic_grid[i - 1][w];
            }
            else
            {
                if (dynamic_grid[i - 1][w]>=INT_MAX ||
                    dynamic_grid[i][w - coins[i - 1]]>=INT_MAX ||
                    dynamic_grid[i - 1][w] + dynamic_grid[i][w - coins[i - 1]]>=INT_MAX
                    )
                {
                    dynamic_grid[i][w] = INT_MAX;
                    continue;
                }
                dynamic_grid[i][w] = dynamic_grid[i - 1][w] + dynamic_grid[i][w - coins[i - 1]];
            }
        }
    }

    //for (auto&mini_vec:dynamic_grid)
    //{
	   // for (auto&num:mini_vec)
	   // {
    //        cout << num << ' ';
	   // }
    //    cout << '\n';
    //}


    if (dynamic_grid[dp_size-1][amount]==0|| dynamic_grid[dp_size - 1][amount] == INT_MAX)
    {
        return 0;
    }
    return dynamic_grid[dp_size - 1][amount];
	//solve06
}


int main()
{
	{
       
        int amount = 5;
        vector<int>coins = { 1, 2, 5 };
        cout << solve06(amount, coins);

        return 0;
	}

	{
        vector<int>coins = { 1,2,5 };
        int amount = 11;
        cout << solve05(coins, amount);
        return 0;
	}

	{
        //coins = [1, 2, 5], amount = 11
        vector<int>coins = { 1,2,5 };
        int amount = 11;
        cout << solve04(coins, amount);
        return 0;
	}

	{
        //nums = [1, 5, 11, 5] true
        vector<int>nums = { 1, 5, 11, 5 };
        cout << solve02(nums);
        return 0;
	}


    /*
    3     // 输入商品的数量 number
	3     // 输入商人售货天数 days
	4 5 6 // 输入仓库限制每件商品的最大持有数量是 item[index]
	1 2 3 // 输入第一件商品每天的价格
	4 3 2 // 输入第二件商品每天的价格
	1 5 3 // 输入第三件商品每天的价格
     */
    //item = [4，5，6]，item_price = [[1,2,3],[4,3,2],[1,5,3]]
    //vector<int>item_limit_vec = { 4,5,6 };
    //vector<vector<int>>item_prices = {{1,2,3},{4,3,2},{1,5,3}};
    //5 95 92 19 83 18 45 41 80 9 17 40 88 59 18 68 84 42 40 46 90 8 96 39 78 38 63 95 43 89 9 56 89 59 96 91 28 70 16 76 10 14 70 96 81 87 93 71 77 32 89 94 93 7 69 25 42 27 77 8 43 5 83 68 31 32 82 87 18 23 93 91 22 3 68 49 87 24 93 47 34 30 9 96 47 5 19 35 50 72 94 47 13

    int item_size, day_size;
    cin >> item_size >> day_size;

    //cout << item_size << day_size;
    vector<int>item_limit_vec(item_size);
    for (int i=0; i< item_size; i++)
    {
        cin >> item_limit_vec[i];
    }

    vector<vector<int>>item_prices(item_size,vector<int>(day_size));
    for (int i=0; i<item_size; i++)
    {
        for (int d=0; d< day_size; d++)
        {
            cin >> item_prices[i][d];
        }
    }

    //for (auto&num:item_limit_vec)
    //{
    //    cout << num << ' ';
    //}

    //for (auto& mini_vec : item_prices)
    //{
    //    for (auto&num:mini_vec)
    //    {
    //        cout << num << ' ';
    //    }
    //    cout << '\n';
    //}

    solve01(item_limit_vec, item_prices);
    //main------
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
